package com.cdream.basic.algorithm.leetcode.bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Lcp07 {
    Map<Integer, List<Integer>> m = new HashMap<>();
    int count = 0;

    public int numWays(int n, int[][] relation, int k) {
        for (int[] r : relation) {
            List<Integer> nextFriend = m.getOrDefault(r[0], new ArrayList<>());
            nextFriend.add(r[1]);
            m.put(r[0], nextFriend);
        }
        dfs(n,k,0);
        return count;
    }

    private void dfs(int n, int k,int currentFriend) {
        if (k==0 && currentFriend==n-1){
            count++;
            return;
        }
        if(k==0){
            return;
        }
        List<Integer> nextFriends = m.get(currentFriend);
        if (nextFriends==null){
            return;
        }
        for (Integer nextFriend : nextFriends) {
            dfs(n,k-1,nextFriend);
        }
    }


    public static void main(String[] args) {
        new Lcp07().numWays(5,new int[][]{{0,2},{2,1},{3,4},{2,3},{1,4},{2,0},{0,4}},3);
    }
}
